package org.algorithm.Sort;

public class QuickSort3 {


    public void quickSort3(int []arr,int start,int end){
        if (start>=end){
            return;
        }
        int piv = arr[start];
        int left = start;
        int right = end;

        int curr = start+1;

        while (curr<=right){
            if (arr[curr]>piv){
                swap(arr,curr,right);
                right--;
            }else if (arr[curr]<piv){
                swap(arr,left,curr);
                curr++;
                left++;
            }else {
                curr++;
            }
        }
        quickSort3(arr,start,left-1);
        quickSort3(arr,right+1,end);
    }


    public void quickSort2(int[] arr, int start, int end) {
        if (start >= end) {
            return;
        }
        int piv = arr[start];
        int i = start;
        int j = end;


        while (i < j) {

            while (i < j && piv <= arr[j]) {
                j--;
            }

            while (i < j && arr[i] <= piv) {
                i++;
            }
            if (i < j) {
                swap(arr, i, j);
            }
        }

        swap(arr, start, j);
        quickSort2(arr, start, j - 1);
        quickSort2(arr, j + 1, end);
    }

    //三路递归
    public void quickSort(int[] arr, int start, int end) {

        if (start >= end) {
            return;
        }

        int piv = arr[start];

        int left = start;
        int right = end;

        int curr = start + 1;

        while (curr <= right) {
            if (arr[curr] > piv) {
                swap(arr, curr, right);
                right--;
            } else if (arr[curr] < piv) {
                swap(arr, curr, left);
                left++;
                curr++;
            } else {
                curr++;
            }
        }

        quickSort(arr, start, left - 1);
        quickSort(arr, right + 1, end);

    }

    private void swap(int[] arr, int index1, int index2) {
        int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }

    public static void main(String[] args) {
        QuickSort3 test = new QuickSort3();
        int[] arr = {1, 3, 6, 5, 10, 68, 52};

        test.quickSort2(arr, 0, arr.length - 1);

        for (int num : arr) {
            System.out.println(num);
        }
    }


}
